#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        // 空字符串可以拆分
        dp[0] = true;
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        // 外层循环, 遍历整个字符串
        for (int i = 0; i < n; i++)
        {
            // 内层循环，遍历每一个结束的位置j
            for (int j = i + 1; j <= n; j++)
            {
                // 检查从i到j的字串是否在字典中，并且dp[i] 是否为true
                string sub = s.substr(i, j - i);
                if (dp[i] && wordSet.find(sub) != wordSet.end())
                {
                    dp[j] = true;
                }
                
            }
            
        }
        return dp[n];
        
    }
};

int main() {
    Solution sol;
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    
    cout << (sol.wordBreak(s, wordDict) ? "true" : "false") << endl;  // 输出: true

    return 0;
}